#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
#include <unordered_set>
#include <queue>
using namespace std;
class Solution {
public:
    string change = "ACGT";
    unordered_set<string> bank, vis;
    int minMutation(string startGene, string endGene, vector<string>& b) {
        queue<string> q;
        int n = startGene.size(), ret = 0;
        for (auto e : b)
        {
            bank.insert(e);
        }
        q.push(startGene);
        vis.insert(startGene);
        if (!bank.count(endGene)) return -1;
        while (!q.empty())
        {
            ret++;
            int sz = q.size();
            while (sz--)
            {
                string tmp = q.front();
                q.pop();
                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < 4; j++)
                    {
                        string str = tmp;
                        str[i] = change[j];
                        if (bank.count(str) && !vis.count(str))
                        {
                            q.push(str);
                            vis.insert(str);
                        }
                        if (str == endGene) return  ret;
                    }
                }
            }

        }
        return -1;
    }
};
int main()
{
    vector<string> b = { "AACCGGTA" };
    Solution().minMutation("AACCGGTT", "AACCGGTA",b );
    return 0;
}